package 牛客.链表;

import 剑指offer.ListNode;

import java.util.HashSet;
import java.util.Set;

public class BM10两个链表的第一个公共结点 {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        //最浪漫的双指针
        //你变成我，走过我走过的路。
        //我变成你，走过你走过的路。
        //然后我们便相遇了..
        ListNode p1=pHead1;
        ListNode p2=pHead2;
        while (p1!=p2) {
            p1 = p1==null? pHead2 : p1.next;
            p2 = p2==null? pHead1 : p2.next;
        }
        return p1;
    }

    public ListNode FindFirstCommonNode2(ListNode pHead1, ListNode pHead2) {
        //哈希表
        Set<ListNode> set=new HashSet<>();
        ListNode p1=pHead1;
        ListNode p2=pHead2;
        while (p1!=null) {
            set.add(p1);
            p1=p1.next;
        }

        while (p2!=null) {
            if (set.contains(p2)) {
                return p2;
            }
            p2=p2.next;
        }
        return null;
    }

    public ListNode FindFirstCommonNode1(ListNode pHead1, ListNode pHead2) {
        ListNode p1=pHead1;
        ListNode p2=pHead2;

        int len1=0;
        int len2=0;
        while (p1!=null) {
           len1++;
           p1=p1.next;
        }
        while (p2!=null) {
            len2++;
            p2=p2.next;
        }

        int step=len1-len2;
        p1=pHead1;
        p2=pHead2;
        if (step>0) {
            //p1先走
            for (int i = 0; i <step; i++) {
                p1=p1.next;
            }
        }else {
            //p2先走
            for (int i = 0; i <Math.abs(step); i++) {
                p2=p2.next;
            }
        }

        while (p1!=p2) {
            p1=p1.next;
            p2=p2.next;
        }

        if (p1!=null) {
            return p1;
        }
        return null;
    }
}
